package DP;

/**
 * 扔鸡蛋问题 https://zhuanlan.zhihu.com/p/41257286
 * 或者 https://mp.weixin.qq.com/s/xn4LjWfaKTPQeCXR0qDqZg
 *
 *
 *
 */
public class EggDP {

    /**
     * 简单的说 还是要明确这个DP，不能说简单的 dp表示最少次数，怎么取还要想明白。。
     *
     * 第k个鸡蛋，在n层楼要多少次
     * 鸡蛋有破和不破的情况,然后，从破和不破里取最大的就是k鸡蛋 n层的次数
     * dp[k][n] = min{dp[k][n], max{dp[k-1][n-1], dp[k][n-x] }}
     */
    public int superEggDrop(int K, int N) {
        int[][] dp = new int[K+1][N+1];

        //先初始化只有1颗的时候,要从1往上扔
        for(int i=0; i<=N; i++) dp[1][i] = i;
        for(int k=2; k<=K; k++){
            for(int n=1;n<=N; n++){
                dp[k][n] = Integer.MAX_VALUE;//初始化为最大
                //开始扔的过程
                for(int x=1; x <= n; x++){
                    //这里取破或者没破两种情况，谁最大，然后，再加上当前这次
                    //注意这里的取值，这里自己写错很多遍了
                    //k个蛋 n层的意思是， 我从1层开始扔，看鸡蛋破没破，这样慢慢上去
                    dp[k][n] = Math.min(dp[k][n], Math.max(dp[k-1][x-1], dp[k][n-x]) + 1);
                }
            }
        }
        return dp[K][N];
    }

    /**
     * dp[k][m]表示，第k个鸡蛋，扔m次能够确定的层数
     * 那在第k个鸡蛋的第m次，就有两种情况，破了和没破。 如果
     *  破了的话，就表示能确定 dp[k][m-1]层是最小，
     *  如果没破就表示，这一层还没没问题，还能网上，当前的层数+1
     */
    public int superEggDrop_II(int K, int N) {
        int[][] dp = new int[K + 1][N + 1];
        //扔的次数肯定在N次内
        for (int m = 1; m <= N; m++) {
            dp[0][m] = 0; // zero egg
            for (int k = 1; k <= K; k++) {//在k个鸡蛋内尝试
                dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
                if (dp[k][m] >= N) {
                    return m;
                }
            }
        }
        return N;
    }



    public static void main(String[] args){
        EggDP e = new EggDP();
        System.out.println( e.superEggDrop_II(2,100) );

    }


}
